package algorithm.swordoff;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树中和为某一值的路径
 * 本题与主站 113 题相同
 *
 * 树的路径定义为 从根节点到叶子节点 的一个像是链表一样的玩意
 */

public class SQ34 {
    public List<List<Integer>> results = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        // if (root == null) return results;
        recursive2(root, new LinkedList<>(), sum);
        return results;
    }


    public void recursive2(TreeNode node,
                           LinkedList<Integer> curr,
                           int remainLength) {
        // 注意不能在这add答案,一个叶子节点还会生出2个null子节点,相当于一个正确答案添加了两遍
        if (node == null) return;

        curr.addLast(node.val);
        // 只有在下面这个if里面才是真正的叶子节点,并且符合答案要求
        if (node.left == null && node.right == null && remainLength == node.val) {
            results.add(new LinkedList<>(curr));
        }
        recursive2(node.left, curr, remainLength - node.val);
        recursive2(node.right, curr, remainLength - node.val);
        curr.removeLast();
    }
}
